#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution
{
public:
    ListNode *detectCycle(ListNode *head)
    {
        ListNode *p = head, *q = head;
        // 这里不能用while (p != q)，因为无法进入循环
        while (1)
        {
            if (q == nullptr || q->next == nullptr)
                return nullptr;
            q = q->next->next;
            p = p->next;
            // 一定要在这里判断
            if (q == p)
                break;
        }
        q = head;
        while (p != q)
        {
            q = q->next;
            p = p->next;
        }
        return p;
    }

    // 答案，注意快慢指针相遇后还要进行处理，因为不一定是入环的第一个节点
    ListNode *detectCycleAns(ListNode *head)
    {
        ListNode *fast = head;
        ListNode *slow = head;
        while (fast != NULL && fast->next != NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
            // 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
            if (slow == fast)
            {
                ListNode *index1 = fast;
                ListNode *index2 = head;
                while (index1 != index2)
                {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index2; // 返回环的入口
            }
        }
        return NULL;
    }
private:
    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };
};

int main()
{
    vector<int> nums = {-21, 10, 17, 8, 4, 26, 5, 35, 33, -7, -16, 27, -12, 6, 29, -12, 5, 9, 20, 14, 14, 2, 13, -24, 21, 23, -21, 5};
    Solution::ListNode *dummyHead = new Solution::ListNode(0);
    Solution::ListNode *dummyHead = new Solution::ListNode(0);

    for (int i : nums)
    {
        Solution::ListNode *node = new Solution::ListNode(i);
        // TODO
    }
    return 0;
}
